package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/8 12:27
 */
public class KMPDemo {


    private static void getNext(int[] next, String pattern) {
        int i, j = 0;
        next[0] = 0;
        for (i = 1; i < pattern.length(); ++i) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

    public static int kmpIndex(String text, String pattern) {
        int[] next = new int[pattern.length()];
        getNext(next, pattern);

        for (int i = 0, j = 0; i < text.length(); ++i) {
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                return (i - pattern.length() + 1);
            }
        }
        return -1;
        // int i = 0, j = 0;
        // while (i < text.length() && j < pattern.length()) {
        //     if (text.charAt(i) == pattern.charAt(j)) {
        //         i++;
        //         j++;
        //     } else if (j > 0) {
        //         j = next[j - 1];
        //     } else {
        //         i++;
        //     }
        // }
        // if (j >= pattern.length()) {
        //     return (i - pattern.length());
        // } else {
        //     return -1;
        // }
    }

    public static void main(String[] args) {
        String text = "gccgaac";
        String pattern = "cga";
        final int i = kmpIndex("abababab", "ababab");
        System.out.println(i);
    }
}
